package com.base.algorithms.binarySearch;

/**
 * @Author: hdhao
 * @Create: 2023/3/26 - 13:44
 * @Version: v1.0
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] source = {2,3,6,8,22,35,55,78,123};

        int res = binarySearchBase(source,55);
        System.out.println(res);

        int rest = binarySearchAdvance(source,55);
        System.out.println(rest);
    }

    /**
     * 二分查找调整版
     * @param source 待查找数据
     * @param target 目标元素
     * @return 元素的下标 找不到返回-1
     */
    /*
    * 与基础版相比较，这个版本的右边界变成了数组的最大长度，它是取不到值的
    * 并且当target < source[mid] 取end = mid ，
    * 同时 while循环的条件变成了begin<end，防止查找的元素不存在时发生死循环
    * */
    private static int binarySearchAdvance(int[] source, int target) {
        int begin = 0;
        int end = source.length;
        while (begin < end){
            int mid = (begin+end) >>> 1;
            if (target < source[mid]){
                end = mid;
            }else if (source[mid] < target){
                begin = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 二分查找
     * @param source 待查找数据
     * @param target 目标元素
     * @return 元素的下标 找不到返回-1
     */
    private static int binarySearchBase(int[] source, int target) {
        //初始下标值
        int begin =0;
        int end = source.length-1;
        while (begin <= end){
            int middle = (begin + end)/2;
            //目标值小于中间值
            if (target < source[middle]){
                end = middle - 1;
            }else if (source[middle] < target){
                begin = middle + 1;
            }else {
                return middle;
            }
        }
        return -1;
    }

}
